#include <cmath>
#include <iostream>
#include <list>
#include <utility>
#include <unordered_map>
using std::cout;
using std::endl;
using std::pair;
using std::list;
using std::unordered_map;

class LRU{

public:
    LRU(int capa)
    :_capacity(capa)
    {
    }
    
    void put(int key,int value){
        //已经存在
        auto it = _k_pos.find(key);
        if(it != _k_pos.end()){
            _kv.splice(_kv.begin(),_kv,it->second); //将结点放到链表
            it->second->second = value;
            return;
        }
        if(_kv.size() == _capacity){ //已满
            int key = _kv.back().first;
            _k_pos.erase(key);
            _kv.pop_back();
        }
        //插入表头
        _kv.push_front(pair(key,value));
        _k_pos[key] = _kv.begin(); //将在list中的位置放到map
    }
    int get(int key){
        auto it = _k_pos.find(key);
        if(it != _k_pos.end()){
            int value = it->second->second;
            _kv.splice(_kv.begin(),_kv,it->second); //将结点放到链表头
            //cout << "begin value:" << _kv.begin()->second<<endl;
            return value;
        }
        return -1;
    }
    void show_kv(){
        for(auto & item:_kv){
            cout << "(" << item.first<<","<< item.second<<") ";
        }
        cout << endl;
    }


private:
    int _capacity;
    list<pair<int,int>> _kv;  
    unordered_map<int,list<pair<int,int>>::iterator> _k_pos;
};

void test(){
    LRU lru(3);
    lru.put(1,1);
    lru.put(2,2);
    lru.put(3,3);
    lru.show_kv();
    lru.put(4,4);
    lru.show_kv();
    lru.put(2,5);

    cout << lru.get(3) << endl;
    lru.show_kv();
    cout << lru.get(2) << endl;
    lru.show_kv();
}

int main()
{
    

    test ();
    return 0;
}

